class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


# class Solution(object):
#     def getIntersectionNode(self, headA, headB):
#         """
#         :type head1, head1: ListNode
#         :rtype: ListNode
#         """
#         # 先求长度
#         lenA, lenB = 0, 0
#         cur = headA
#
#         while cur:
#             cur = cur.next
#             lenA += 1
#
#         cur = headB
#         while cur:
#             cur = cur.next
#             lenB += 1
#
#         curA, curB = headA, headB
#         if lenA > lenB:
#             curA, curB = curB, curA
#             lenA, lenB = lenB, lenA
#
#         for _ in range(lenB - lenA):
#             curB = curB.next
#
#         while curA:
#             if curA == curB:
#                 return curA
#             curA, curB = curA.next, curB.next
#         return None


# 代码复用版
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        lenA = self.getLength(headA)
        lenB = self.getLength(headB)
        if lenA > lenB:
            headA = self.moveForward(headA,lenA - lenB)
        else:
            headB = self.moveForward(headB,lenB - lenA)

        while headA and headB:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next

        return None



    # 获取长度
    def getLength(self, head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    def moveForward(self,head,steps):
        while steps:
            head = head.next
            steps -= 1
        return head